1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.Lists.newArrayList;
20 import static com.google.common.collect.MapMakerInternalMap.DISCARDING_QUEUE;
21 import static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD;
22 import static com.google.common.collect.MapMakerInternalMap.nullEntry;
23 import static com.google.common.collect.MapMakerInternalMap.unset;
24 import static java.util.concurrent.TimeUnit.SECONDS;
25
26 import com.google.common.base.Equivalence;
27 import com.google.common.base.Ticker;
28 import com.google.common.collect.MapMaker.RemovalCause;
29 import com.google.common.collect.MapMaker.RemovalListener;
30 import com.google.common.collect.MapMaker.RemovalNotification;
31 import com.google.common.collect.MapMakerInternalMap.EntryFactory;
32 import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
33 import com.google.common.collect.MapMakerInternalMap.Segment;
34 import com.google.common.collect.MapMakerInternalMap.Strength;
35 import com.google.common.collect.MapMakerInternalMap.ValueReference;
36 import com.google.common.testing.NullPointerTester;
37
38 import junit.framework.TestCase;
39
40 import java.lang.ref.Reference;
41 import java.lang.ref.ReferenceQueue;
42 import java.util.Iterator;
43 import java.util.LinkedHashMap;
44 import java.util.List;
45 import java.util.Map;
46 import java.util.Random;
47 import java.util.concurrent.ConcurrentLinkedQueue;
48 import java.util.concurrent.TimeUnit;
49 import java.util.concurrent.atomic.AtomicInteger;
50 import java.util.concurrent.atomic.AtomicReferenceArray;
51
52
53
54
55 @SuppressWarnings("deprecation")
56 public class MapMakerInternalMapTest extends TestCase {
57
58 static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5;
59
60 private static <K, V> MapMakerInternalMap<K, V> makeMap(GenericMapMaker<K, V> maker) {
61 return new MapMakerInternalMap<K, V>((MapMaker) maker);
62 }
63
64 private static <K, V> MapMakerInternalMap<K, V> makeMap(MapMaker maker) {
65 return new MapMakerInternalMap<K, V>(maker);
66 }
67
68 private static MapMaker createMapMaker() {
69 MapMaker maker = new MapMaker();
70 maker.useCustomMap = true;
71 return maker;
72 }
73
74
75
76 public void testDefaults() {
77 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker());
78
79 assertSame(Strength.STRONG, map.keyStrength);
80 assertSame(Strength.STRONG, map.valueStrength);
81 assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
82 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
83
84 assertEquals(0, map.expireAfterAccessNanos);
85 assertEquals(0, map.expireAfterWriteNanos);
86 assertEquals(MapMaker.UNSET_INT, map.maximumSize);
87
88 assertSame(EntryFactory.STRONG, map.entryFactory);
89 assertSame(MapMaker.NullListener.INSTANCE, map.removalListener);
90 assertSame(DISCARDING_QUEUE, map.removalNotificationQueue);
91 assertSame(Ticker.systemTicker(), map.ticker);
92
93 assertEquals(4, map.concurrencyLevel);
94
95
96 assertEquals(4, map.segments.length);
97
98 assertEquals(16 / map.segments.length, map.segments[0].table.length());
99
100 assertFalse(map.evictsBySize());
101 assertFalse(map.expires());
102 assertFalse(map.expiresAfterWrite());
103 assertFalse(map.expiresAfterAccess());
104 }
105
106 public void testSetKeyEquivalence() {
107 Equivalence<Object> testEquivalence = new Equivalence<Object>() {
108 @Override
109 protected boolean doEquivalent(Object a, Object b) {
110 return false;
111 }
112
113 @Override
114 protected int doHash(Object t) {
115 return 0;
116 }
117 };
118
119 MapMakerInternalMap<Object, Object> map =
120 makeMap(createMapMaker().keyEquivalence(testEquivalence));
121 assertSame(testEquivalence, map.keyEquivalence);
122 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
123 }
124
125 public void testSetConcurrencyLevel() {
126
127
128 checkConcurrencyLevel(1, 1);
129 checkConcurrencyLevel(2, 2);
130 checkConcurrencyLevel(3, 4);
131 checkConcurrencyLevel(4, 4);
132 checkConcurrencyLevel(5, 8);
133 checkConcurrencyLevel(6, 8);
134 checkConcurrencyLevel(7, 8);
135 checkConcurrencyLevel(8, 8);
136 }
137
138 private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) {
139 MapMakerInternalMap<Object, Object> map =
140 makeMap(createMapMaker().concurrencyLevel(concurrencyLevel));
141 assertEquals(segmentCount, map.segments.length);
142 }
143
144 public void testSetInitialCapacity() {
145
146
147 checkInitialCapacity(1, 0, 1);
148 checkInitialCapacity(1, 1, 1);
149 checkInitialCapacity(1, 2, 2);
150 checkInitialCapacity(1, 3, 4);
151 checkInitialCapacity(1, 4, 4);
152 checkInitialCapacity(1, 5, 8);
153 checkInitialCapacity(1, 6, 8);
154 checkInitialCapacity(1, 7, 8);
155 checkInitialCapacity(1, 8, 8);
156
157 checkInitialCapacity(2, 0, 1);
158 checkInitialCapacity(2, 1, 1);
159 checkInitialCapacity(2, 2, 1);
160 checkInitialCapacity(2, 3, 2);
161 checkInitialCapacity(2, 4, 2);
162 checkInitialCapacity(2, 5, 4);
163 checkInitialCapacity(2, 6, 4);
164 checkInitialCapacity(2, 7, 4);
165 checkInitialCapacity(2, 8, 4);
166
167 checkInitialCapacity(4, 0, 1);
168 checkInitialCapacity(4, 1, 1);
169 checkInitialCapacity(4, 2, 1);
170 checkInitialCapacity(4, 3, 1);
171 checkInitialCapacity(4, 4, 1);
172 checkInitialCapacity(4, 5, 2);
173 checkInitialCapacity(4, 6, 2);
174 checkInitialCapacity(4, 7, 2);
175 checkInitialCapacity(4, 8, 2);
176 }
177
178 private static void checkInitialCapacity(
179 int concurrencyLevel, int initialCapacity, int segmentSize) {
180 MapMakerInternalMap<Object, Object> map = makeMap(
181 createMapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity));
182 for (int i = 0; i < map.segments.length; i++) {
183 assertEquals(segmentSize, map.segments[i].table.length());
184 }
185 }
186
187 public void testSetMaximumSize() {
188
189
190 for (int maxSize = 1; maxSize < 8; maxSize++) {
191 checkMaximumSize(1, 8, maxSize);
192 checkMaximumSize(2, 8, maxSize);
193 checkMaximumSize(4, 8, maxSize);
194 checkMaximumSize(8, 8, maxSize);
195 }
196
197 checkMaximumSize(1, 8, Integer.MAX_VALUE);
198 checkMaximumSize(2, 8, Integer.MAX_VALUE);
199 checkMaximumSize(4, 8, Integer.MAX_VALUE);
200 checkMaximumSize(8, 8, Integer.MAX_VALUE);
201
202
203
204 for (int capacity = 0; capacity < 8; capacity++) {
205 checkMaximumSize(1, capacity, 4);
206 checkMaximumSize(2, capacity, 4);
207 checkMaximumSize(4, capacity, 4);
208 checkMaximumSize(8, capacity, 4);
209 }
210 }
211
212 private static void checkMaximumSize(int concurrencyLevel, int initialCapacity, int maxSize) {
213 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
214 .concurrencyLevel(concurrencyLevel)
215 .initialCapacity(initialCapacity)
216 .maximumSize(maxSize));
217 int totalCapacity = 0;
218 for (int i = 0; i < map.segments.length; i++) {
219 totalCapacity += map.segments[i].maxSegmentSize;
220 }
221 assertTrue("totalCapcity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity <= maxSize);
222 }
223
224 public void testSetWeakKeys() {
225 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakKeys());
226 checkStrength(map, Strength.WEAK, Strength.STRONG);
227 assertSame(EntryFactory.WEAK, map.entryFactory);
228 }
229
230 public void testSetWeakValues() {
231 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakValues());
232 checkStrength(map, Strength.STRONG, Strength.WEAK);
233 assertSame(EntryFactory.STRONG, map.entryFactory);
234 }
235
236 public void testSetSoftValues() {
237 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().softValues());
238 checkStrength(map, Strength.STRONG, Strength.SOFT);
239 assertSame(EntryFactory.STRONG, map.entryFactory);
240 }
241
242 private static void checkStrength(
243 MapMakerInternalMap<Object, Object> map, Strength keyStrength, Strength valueStrength) {
244 assertSame(keyStrength, map.keyStrength);
245 assertSame(valueStrength, map.valueStrength);
246 assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence);
247 assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence);
248 }
249
250 public void testSetExpireAfterWrite() {
251 long duration = 42;
252 TimeUnit unit = SECONDS;
253 MapMakerInternalMap<Object, Object> map =
254 makeMap(createMapMaker().expireAfterWrite(duration, unit));
255 assertEquals(unit.toNanos(duration), map.expireAfterWriteNanos);
256 }
257
258 public void testSetExpireAfterAccess() {
259 long duration = 42;
260 TimeUnit unit = SECONDS;
261 MapMakerInternalMap<Object, Object> map =
262 makeMap(createMapMaker().expireAfterAccess(duration, unit));
263 assertEquals(unit.toNanos(duration), map.expireAfterAccessNanos);
264 }
265
266 public void testSetRemovalListener() {
267 RemovalListener<Object, Object> testListener = new RemovalListener<Object, Object>() {
268 @Override
269 public void onRemoval(RemovalNotification<Object, Object> notification) {}
270 };
271 MapMakerInternalMap<Object, Object> map =
272 makeMap(createMapMaker().removalListener(testListener));
273 assertSame(testListener, map.removalListener);
274 }
275
276
277
278 public void testRemovalListener_explicit() {
279 QueuingRemovalListener<Object, Object> listener =
280 new QueuingRemovalListener<Object, Object>();
281 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
282 .removalListener(listener));
283 assertTrue(listener.isEmpty());
284
285 Object one = new Object();
286 Object two = new Object();
287 Object three = new Object();
288 Object four = new Object();
289 Object five = new Object();
290 Object six = new Object();
291
292 map.put(one, two);
293 map.remove(one);
294 assertNotified(listener, one, two, RemovalCause.EXPLICIT);
295
296 map.put(two, three);
297 map.remove(two, three);
298 assertNotified(listener, two, three, RemovalCause.EXPLICIT);
299
300 map.put(three, four);
301 Iterator<?> i = map.entrySet().iterator();
302 i.next();
303 i.remove();
304 assertNotified(listener, three, four, RemovalCause.EXPLICIT);
305
306 map.put(four, five);
307 i = map.keySet().iterator();
308 i.next();
309 i.remove();
310 assertNotified(listener, four, five, RemovalCause.EXPLICIT);
311
312 map.put(five, six);
313 i = map.values().iterator();
314 i.next();
315 i.remove();
316 assertNotified(listener, five, six, RemovalCause.EXPLICIT);
317
318 assertTrue(listener.isEmpty());
319 }
320
321 public void testRemovalListener_replaced() {
322 QueuingRemovalListener<Object, Object> listener =
323 new QueuingRemovalListener<Object, Object>();
324 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
325 .removalListener(listener));
326 assertTrue(listener.isEmpty());
327
328 Object one = new Object();
329 Object two = new Object();
330 Object three = new Object();
331 Object four = new Object();
332 Object five = new Object();
333 Object six = new Object();
334
335 map.put(one, two);
336 map.put(one, three);
337 assertNotified(listener, one, two, RemovalCause.REPLACED);
338
339 Map<Object, Object> newMap = ImmutableMap.of(one, four);
340 map.putAll(newMap);
341 assertNotified(listener, one, three, RemovalCause.REPLACED);
342
343 map.replace(one, five);
344 assertNotified(listener, one, four, RemovalCause.REPLACED);
345
346 map.replace(one, five, six);
347 assertNotified(listener, one, five, RemovalCause.REPLACED);
348 }
349
350 public void testRemovalListener_collected() {
351 QueuingRemovalListener<Object, Object> listener =
352 new QueuingRemovalListener<Object, Object>();
353 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
354 .concurrencyLevel(1)
355 .softValues()
356 .removalListener(listener));
357 Segment<Object, Object> segment = map.segments[0];
358 assertTrue(listener.isEmpty());
359
360 Object one = new Object();
361 Object two = new Object();
362 Object three = new Object();
363
364 map.put(one, two);
365 map.put(two, three);
366 assertTrue(listener.isEmpty());
367
368 int hash = map.hash(one);
369 ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
370 map.reclaimValue(entry.getValueReference());
371 assertNotified(listener, one, two, RemovalCause.COLLECTED);
372
373 assertTrue(listener.isEmpty());
374 }
375
376 public void testRemovalListener_size() {
377 QueuingRemovalListener<Object, Object> listener =
378 new QueuingRemovalListener<Object, Object>();
379 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
380 .concurrencyLevel(1)
381 .maximumSize(2)
382 .removalListener(listener));
383 assertTrue(listener.isEmpty());
384
385 Object one = new Object();
386 Object two = new Object();
387 Object three = new Object();
388 Object four = new Object();
389
390 map.put(one, two);
391 map.put(two, three);
392 assertTrue(listener.isEmpty());
393 map.put(three, four);
394 assertNotified(listener, one, two, RemovalCause.SIZE);
395
396 assertTrue(listener.isEmpty());
397 }
398
399 static <K, V> void assertNotified(
400 QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause) {
401 RemovalNotification<K, V> notification = listener.remove();
402 assertSame(key, notification.getKey());
403 assertSame(value, notification.getValue());
404 assertSame(cause, notification.getCause());
405 }
406
407
408
409 public void testNewEntry() {
410 for (MapMaker maker : allEntryTypeMakers()) {
411 MapMakerInternalMap<Object, Object> map = makeMap(maker);
412
413 Object keyOne = new Object();
414 Object valueOne = new Object();
415 int hashOne = map.hash(keyOne);
416 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
417 ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne);
418 assertSame(valueOne, valueRefOne.get());
419 entryOne.setValueReference(valueRefOne);
420
421 assertSame(keyOne, entryOne.getKey());
422 assertEquals(hashOne, entryOne.getHash());
423 assertNull(entryOne.getNext());
424 assertSame(valueRefOne, entryOne.getValueReference());
425
426 Object keyTwo = new Object();
427 Object valueTwo = new Object();
428 int hashTwo = map.hash(keyTwo);
429 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
430 ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo);
431 assertSame(valueTwo, valueRefTwo.get());
432 entryTwo.setValueReference(valueRefTwo);
433
434 assertSame(keyTwo, entryTwo.getKey());
435 assertEquals(hashTwo, entryTwo.getHash());
436 assertSame(entryOne, entryTwo.getNext());
437 assertSame(valueRefTwo, entryTwo.getValueReference());
438 }
439 }
440
441 public void testCopyEntry() {
442 for (MapMaker maker : allEntryTypeMakers()) {
443 MapMakerInternalMap<Object, Object> map = makeMap(maker);
444
445 Object keyOne = new Object();
446 Object valueOne = new Object();
447 int hashOne = map.hash(keyOne);
448 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
449 entryOne.setValueReference(map.newValueReference(entryOne, valueOne));
450
451 Object keyTwo = new Object();
452 Object valueTwo = new Object();
453 int hashTwo = map.hash(keyTwo);
454 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
455 entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo));
456 if (map.evictsBySize()) {
457 MapMakerInternalMap.connectEvictables(entryOne, entryTwo);
458 }
459 if (map.expires()) {
460 MapMakerInternalMap.connectExpirables(entryOne, entryTwo);
461 }
462 assertConnected(map, entryOne, entryTwo);
463
464 ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null);
465 assertSame(keyOne, entryOne.getKey());
466 assertEquals(hashOne, entryOne.getHash());
467 assertNull(entryOne.getNext());
468 assertSame(valueOne, copyOne.getValueReference().get());
469 assertConnected(map, copyOne, entryTwo);
470
471 ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne);
472 assertSame(keyTwo, copyTwo.getKey());
473 assertEquals(hashTwo, copyTwo.getHash());
474 assertSame(copyOne, copyTwo.getNext());
475 assertSame(valueTwo, copyTwo.getValueReference().get());
476 assertConnected(map, copyOne, copyTwo);
477 }
478 }
479
480 private static <K, V> void assertConnected(
481 MapMakerInternalMap<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) {
482 if (map.evictsBySize()) {
483 assertSame(two, one.getNextEvictable());
484 }
485 if (map.expires()) {
486 assertSame(two, one.getNextExpirable());
487 }
488 }
489
490 public void testSegmentGetAndContains() {
491 MapMakerInternalMap<Object, Object> map =
492 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
493 Segment<Object, Object> segment = map.segments[0];
494
495
496 Object key = new Object();
497 int hash = map.hash(key);
498 Object value = new Object();
499 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
500 int index = hash & (table.length() - 1);
501
502 ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null);
503 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
504 entry.setValueReference(valueRef);
505
506 assertNull(segment.get(key, hash));
507
508
509 table.set(index, entry);
510 assertNull(segment.get(key, hash));
511 assertFalse(segment.containsKey(key, hash));
512 assertFalse(segment.containsValue(value));
513
514
515 segment.count++;
516 assertSame(value, segment.get(key, hash));
517 assertTrue(segment.containsKey(key, hash));
518 assertTrue(segment.containsValue(value));
519
520 assertNull(segment.get(new Object(), hash));
521
522
523 DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry);
524 Object nullValue = new Object();
525 ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue);
526 nullEntry.setValueReference(nullValueRef);
527 table.set(index, nullEntry);
528
529 assertSame(value, segment.get(key, hash));
530 assertTrue(segment.containsKey(key, hash));
531 assertTrue(segment.containsValue(value));
532 assertFalse(segment.containsValue(nullValue));
533
534
535 DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry);
536 Object dummyValue = new Object();
537 ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue);
538 dummy.setValueReference(dummyValueRef);
539 table.set(index, dummy);
540 assertSame(value, segment.get(key, hash));
541 assertTrue(segment.containsKey(key, hash));
542 assertTrue(segment.containsValue(value));
543 assertTrue(segment.containsValue(dummyValue));
544
545
546 dummy = DummyEntry.create(key, hash, entry);
547 dummyValue = new Object();
548 dummyValueRef = map.newValueReference(dummy, dummyValue);
549 dummy.setValueReference(dummyValueRef);
550 table.set(index, dummy);
551
552 assertSame(dummyValue, segment.get(key, hash));
553 assertTrue(segment.containsKey(key, hash));
554 assertTrue(segment.containsValue(value));
555 assertTrue(segment.containsValue(dummyValue));
556
557
558 dummy.setExpirationTime(0);
559 assertNull(segment.get(key, hash));
560 assertFalse(segment.containsKey(key, hash));
561 assertTrue(segment.containsValue(value));
562 assertFalse(segment.containsValue(dummyValue));
563 }
564
565 public void testSegmentReplaceValue() {
566 MapMakerInternalMap<Object, Object> map =
567 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
568 Segment<Object, Object> segment = map.segments[0];
569
570
571 Object key = new Object();
572 int hash = map.hash(key);
573 Object oldValue = new Object();
574 Object newValue = new Object();
575 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
576 int index = hash & (table.length() - 1);
577
578 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
579 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
580 entry.setValueReference(oldValueRef);
581
582
583 assertFalse(segment.replace(key, hash, oldValue, newValue));
584 assertEquals(0, segment.count);
585
586
587 table.set(index, entry);
588 segment.count++;
589 assertEquals(1, segment.count);
590 assertSame(oldValue, segment.get(key, hash));
591 assertTrue(segment.replace(key, hash, oldValue, newValue));
592 assertEquals(1, segment.count);
593 assertSame(newValue, segment.get(key, hash));
594
595
596 assertFalse(segment.replace(key, hash, oldValue, newValue));
597 assertEquals(1, segment.count);
598 assertSame(newValue, segment.get(key, hash));
599
600
601 entry.setValueReference(oldValueRef);
602 assertSame(oldValue, segment.get(key, hash));
603 oldValueRef.clear(null);
604 assertFalse(segment.replace(key, hash, oldValue, newValue));
605 assertEquals(0, segment.count);
606 assertNull(segment.get(key, hash));
607 }
608
609 public void testSegmentReplace() {
610 MapMakerInternalMap<Object, Object> map =
611 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
612 Segment<Object, Object> segment = map.segments[0];
613
614
615 Object key = new Object();
616 int hash = map.hash(key);
617 Object oldValue = new Object();
618 Object newValue = new Object();
619 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
620 int index = hash & (table.length() - 1);
621
622 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
623 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
624 entry.setValueReference(oldValueRef);
625
626
627 assertNull(segment.replace(key, hash, newValue));
628 assertEquals(0, segment.count);
629
630
631 table.set(index, entry);
632 segment.count++;
633 assertEquals(1, segment.count);
634 assertSame(oldValue, segment.get(key, hash));
635 assertSame(oldValue, segment.replace(key, hash, newValue));
636 assertEquals(1, segment.count);
637 assertSame(newValue, segment.get(key, hash));
638
639
640 entry.setValueReference(oldValueRef);
641 assertSame(oldValue, segment.get(key, hash));
642 oldValueRef.clear(null);
643 assertNull(segment.replace(key, hash, newValue));
644 assertEquals(0, segment.count);
645 assertNull(segment.get(key, hash));
646 }
647
648 public void testSegmentPut() {
649 MapMakerInternalMap<Object, Object> map =
650 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
651 Segment<Object, Object> segment = map.segments[0];
652
653
654 Object key = new Object();
655 int hash = map.hash(key);
656 Object oldValue = new Object();
657 Object newValue = new Object();
658
659
660 assertEquals(0, segment.count);
661 assertNull(segment.put(key, hash, oldValue, false));
662 assertEquals(1, segment.count);
663
664
665 assertSame(oldValue, segment.put(key, hash, newValue, false));
666 assertEquals(1, segment.count);
667 assertSame(newValue, segment.get(key, hash));
668
669
670 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
671 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
672 entry.setValueReference(oldValueRef);
673 assertSame(oldValue, segment.get(key, hash));
674 oldValueRef.clear(null);
675 assertNull(segment.put(key, hash, newValue, false));
676 assertEquals(1, segment.count);
677 assertSame(newValue, segment.get(key, hash));
678 }
679
680 public void testSegmentPutIfAbsent() {
681 MapMakerInternalMap<Object, Object> map =
682 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
683 Segment<Object, Object> segment = map.segments[0];
684
685
686 Object key = new Object();
687 int hash = map.hash(key);
688 Object oldValue = new Object();
689 Object newValue = new Object();
690
691
692 assertEquals(0, segment.count);
693 assertNull(segment.put(key, hash, oldValue, true));
694 assertEquals(1, segment.count);
695
696
697 assertSame(oldValue, segment.put(key, hash, newValue, true));
698 assertEquals(1, segment.count);
699 assertSame(oldValue, segment.get(key, hash));
700
701
702 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
703 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
704 entry.setValueReference(oldValueRef);
705 assertSame(oldValue, segment.get(key, hash));
706 oldValueRef.clear(null);
707 assertNull(segment.put(key, hash, newValue, true));
708 assertEquals(1, segment.count);
709 assertSame(newValue, segment.get(key, hash));
710 }
711
712 public void testSegmentPut_expand() {
713 MapMakerInternalMap<Object, Object> map =
714 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
715 Segment<Object, Object> segment = map.segments[0];
716 assertEquals(1, segment.table.length());
717
718 int count = 1024;
719 for (int i = 0; i < count; i++) {
720 Object key = new Object();
721 Object value = new Object();
722 int hash = map.hash(key);
723 assertNull(segment.put(key, hash, value, false));
724 assertTrue(segment.table.length() > i);
725 }
726 }
727
728 public void testSegmentPut_evict() {
729 int maxSize = 10;
730 MapMakerInternalMap<Object, Object> map =
731 makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize));
732
733
734 int originalCount = 1024;
735 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
736 for (int i = 0; i < originalCount; i++) {
737 Object key = new Object();
738 Object value = new Object();
739 map.put(key, value);
740 originalMap.put(key, value);
741 if (i >= maxSize) {
742 Iterator<Object> it = originalMap.keySet().iterator();
743 it.next();
744 it.remove();
745 }
746 assertEquals(originalMap, map);
747 }
748 }
749
750 public void testSegmentRemove() {
751 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
752 Segment<Object, Object> segment = map.segments[0];
753
754 Object key = new Object();
755 int hash = map.hash(key);
756 Object oldValue = new Object();
757 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
758 int index = hash & (table.length() - 1);
759
760 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
761 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
762 entry.setValueReference(oldValueRef);
763
764
765 assertEquals(0, segment.count);
766 assertNull(segment.remove(key, hash));
767 assertEquals(0, segment.count);
768
769
770 table.set(index, entry);
771 segment.count++;
772 assertEquals(1, segment.count);
773 assertSame(oldValue, segment.get(key, hash));
774 assertSame(oldValue, segment.remove(key, hash));
775 assertEquals(0, segment.count);
776 assertNull(segment.get(key, hash));
777
778
779 table.set(index, entry);
780 segment.count++;
781 assertEquals(1, segment.count);
782 assertSame(oldValue, segment.get(key, hash));
783 oldValueRef.clear(null);
784 assertNull(segment.remove(key, hash));
785 assertEquals(0, segment.count);
786 assertNull(segment.get(key, hash));
787 }
788
789 public void testSegmentRemoveValue() {
790 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
791 Segment<Object, Object> segment = map.segments[0];
792
793 Object key = new Object();
794 int hash = map.hash(key);
795 Object oldValue = new Object();
796 Object newValue = new Object();
797 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
798 int index = hash & (table.length() - 1);
799
800 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
801 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
802 entry.setValueReference(oldValueRef);
803
804
805 assertEquals(0, segment.count);
806 assertNull(segment.remove(key, hash));
807 assertEquals(0, segment.count);
808
809
810 table.set(index, entry);
811 segment.count++;
812 assertEquals(1, segment.count);
813 assertSame(oldValue, segment.get(key, hash));
814 assertTrue(segment.remove(key, hash, oldValue));
815 assertEquals(0, segment.count);
816 assertNull(segment.get(key, hash));
817
818
819 table.set(index, entry);
820 segment.count++;
821 assertEquals(1, segment.count);
822 assertSame(oldValue, segment.get(key, hash));
823 assertFalse(segment.remove(key, hash, newValue));
824 assertEquals(1, segment.count);
825 assertSame(oldValue, segment.get(key, hash));
826
827
828 assertSame(oldValue, segment.get(key, hash));
829 oldValueRef.clear(null);
830 assertFalse(segment.remove(key, hash, oldValue));
831 assertEquals(0, segment.count);
832 assertNull(segment.get(key, hash));
833 }
834
835 public void testExpand() {
836 MapMakerInternalMap<Object, Object> map =
837 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
838 Segment<Object, Object> segment = map.segments[0];
839 assertEquals(1, segment.table.length());
840
841
842 int originalCount = 1024;
843 ReferenceEntry<Object, Object> entry = null;
844 for (int i = 0; i < originalCount; i++) {
845 Object key = new Object();
846 Object value = new Object();
847 int hash = map.hash(key);
848
849 entry = map.newEntry(key, hash, entry);
850 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
851 entry.setValueReference(valueRef);
852 }
853 segment.table.set(0, entry);
854 segment.count = originalCount;
855 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
856 assertEquals(originalCount, originalMap.size());
857 assertEquals(originalMap, map);
858
859 for (int i = 1; i <= originalCount * 2; i *= 2) {
860 if (i > 1) {
861 segment.expand();
862 }
863 assertEquals(i, segment.table.length());
864 assertEquals(originalCount, countLiveEntries(map));
865 assertEquals(originalCount, segment.count);
866 assertEquals(originalMap, map);
867 }
868 }
869
870 public void testReclaimKey() {
871 CountingRemovalListener<Object, Object> listener =
872 new CountingRemovalListener<Object, Object>();
873 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
874 .concurrencyLevel(1)
875 .initialCapacity(1)
876 .maximumSize(SMALL_MAX_SIZE)
877 .expireAfterWrite(99999, SECONDS)
878 .removalListener(listener));
879 Segment<Object, Object> segment = map.segments[0];
880 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
881 assertEquals(1, table.length());
882
883
884 Object keyOne = new Object();
885 Object valueOne = new Object();
886 int hashOne = map.hash(keyOne);
887 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
888 Object keyTwo = new Object();
889 Object valueTwo = new Object();
890 int hashTwo = map.hash(keyTwo);
891 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
892 Object keyThree = new Object();
893 Object valueThree = new Object();
894 int hashThree = map.hash(keyThree);
895 DummyEntry<Object, Object> entryThree =
896 createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
897
898
899 assertEquals(0, listener.getCount());
900 assertFalse(segment.reclaimKey(entryOne, hashOne));
901 assertEquals(0, listener.getCount());
902 table.set(0, entryOne);
903 assertFalse(segment.reclaimKey(entryTwo, hashTwo));
904 assertEquals(0, listener.getCount());
905 table.set(0, entryTwo);
906 assertFalse(segment.reclaimKey(entryThree, hashThree));
907 assertEquals(0, listener.getCount());
908
909
910 table.set(0, entryOne);
911 segment.count = 1;
912 assertTrue(segment.reclaimKey(entryOne, hashOne));
913 assertEquals(1, listener.getCount());
914 assertSame(keyOne, listener.getLastEvictedKey());
915 assertSame(valueOne, listener.getLastEvictedValue());
916 assertTrue(map.removalNotificationQueue.isEmpty());
917 assertFalse(segment.evictionQueue.contains(entryOne));
918 assertFalse(segment.expirationQueue.contains(entryOne));
919 assertEquals(0, segment.count);
920 assertNull(table.get(0));
921 }
922
923 public void testRemoveFromChain() {
924 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
925 Segment<Object, Object> segment = map.segments[0];
926
927
928 Object keyOne = new Object();
929 Object valueOne = new Object();
930 int hashOne = map.hash(keyOne);
931 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
932 Object keyTwo = new Object();
933 Object valueTwo = new Object();
934 int hashTwo = map.hash(keyTwo);
935 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
936 Object keyThree = new Object();
937 Object valueThree = new Object();
938 int hashThree = map.hash(keyThree);
939 DummyEntry<Object, Object> entryThree =
940 createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
941
942
943 assertNull(segment.removeFromChain(entryOne, entryOne));
944
945
946 assertSame(entryOne, segment.removeFromChain(entryTwo, entryTwo));
947
948
949 ReferenceEntry<Object, Object> newFirst = segment.removeFromChain(entryThree, entryTwo);
950 assertSame(keyThree, newFirst.getKey());
951 assertSame(valueThree, newFirst.getValueReference().get());
952 assertEquals(hashThree, newFirst.getHash());
953 assertSame(entryOne, newFirst.getNext());
954
955
956 newFirst = segment.removeFromChain(entryThree, entryOne);
957 assertSame(keyTwo, newFirst.getKey());
958 assertSame(valueTwo, newFirst.getValueReference().get());
959 assertEquals(hashTwo, newFirst.getHash());
960 newFirst = newFirst.getNext();
961 assertSame(keyThree, newFirst.getKey());
962 assertSame(valueThree, newFirst.getValueReference().get());
963 assertEquals(hashThree, newFirst.getHash());
964 assertNull(newFirst.getNext());
965 }
966
967 public void testExpand_cleanup() {
968 MapMakerInternalMap<Object, Object> map =
969 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
970 Segment<Object, Object> segment = map.segments[0];
971 assertEquals(1, segment.table.length());
972
973
974
975 int originalCount = 1024;
976 ReferenceEntry<Object, Object> entry = null;
977 for (int i = 0; i < originalCount; i++) {
978 Object key = new Object();
979 Object value = (i % 3 == 0) ? null : new Object();
980 int hash = map.hash(key);
981 if (i % 3 == 1) {
982 key = null;
983 }
984
985 entry = DummyEntry.create(key, hash, entry);
986 ValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
987 entry.setValueReference(valueRef);
988 }
989 segment.table.set(0, entry);
990 segment.count = originalCount;
991 int liveCount = originalCount / 3;
992 assertEquals(1, segment.table.length());
993 assertEquals(liveCount, countLiveEntries(map));
994 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
995 assertEquals(liveCount, originalMap.size());
996
997
998 for (int i = 1; i <= originalCount * 2; i *= 2) {
999 if (i > 1) {
1000 segment.expand();
1001 }
1002 assertEquals(i, segment.table.length());
1003 assertEquals(liveCount, countLiveEntries(map));
1004
1005 assertTrue(segment.count >= liveCount);
1006 assertTrue(segment.count <= originalCount);
1007 assertEquals(originalMap, ImmutableMap.copyOf(map));
1008 }
1009 }
1010
1011 private static <K, V> int countLiveEntries(MapMakerInternalMap<K, V> map) {
1012 int result = 0;
1013 for (Segment<K, V> segment : map.segments) {
1014 AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
1015 for (int i = 0; i < table.length(); i++) {
1016 for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
1017 if (map.isLive(e)) {
1018 result++;
1019 }
1020 }
1021 }
1022 }
1023 return result;
1024 }
1025
1026 public void testClear() {
1027 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1028 .concurrencyLevel(1)
1029 .initialCapacity(1)
1030 .maximumSize(SMALL_MAX_SIZE)
1031 .expireAfterWrite(99999, SECONDS));
1032 Segment<Object, Object> segment = map.segments[0];
1033 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1034 assertEquals(1, table.length());
1035
1036 Object key = new Object();
1037 Object value = new Object();
1038 int hash = map.hash(key);
1039 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1040 segment.recordWrite(entry);
1041 segment.table.set(0, entry);
1042 segment.readCount.incrementAndGet();
1043 segment.count = 1;
1044
1045 assertSame(entry, table.get(0));
1046 assertSame(entry, segment.evictionQueue.peek());
1047 assertSame(entry, segment.expirationQueue.peek());
1048
1049 segment.clear();
1050 assertNull(table.get(0));
1051 assertTrue(segment.evictionQueue.isEmpty());
1052 assertTrue(segment.expirationQueue.isEmpty());
1053 assertEquals(0, segment.readCount.get());
1054 assertEquals(0, segment.count);
1055 }
1056
1057 public void testRemoveEntry() {
1058 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1059 .concurrencyLevel(1)
1060 .initialCapacity(1)
1061 .maximumSize(SMALL_MAX_SIZE)
1062 .expireAfterWrite(99999, SECONDS)
1063 .removalListener(new CountingRemovalListener<Object, Object>()));
1064 Segment<Object, Object> segment = map.segments[0];
1065 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1066 assertEquals(1, table.length());
1067
1068 Object key = new Object();
1069 Object value = new Object();
1070 int hash = map.hash(key);
1071 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1072
1073
1074 assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1075
1076
1077 segment.recordWrite(entry);
1078 table.set(0, entry);
1079 segment.count = 1;
1080 assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1081 assertNotificationEnqueued(map, key, value);
1082 assertTrue(map.removalNotificationQueue.isEmpty());
1083 assertFalse(segment.evictionQueue.contains(entry));
1084 assertFalse(segment.expirationQueue.contains(entry));
1085 assertEquals(0, segment.count);
1086 assertNull(table.get(0));
1087 }
1088
1089 public void testReclaimValue() {
1090 CountingRemovalListener<Object, Object> listener =
1091 new CountingRemovalListener<Object, Object>();
1092 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1093 .concurrencyLevel(1)
1094 .initialCapacity(1)
1095 .maximumSize(SMALL_MAX_SIZE)
1096 .expireAfterWrite(99999, SECONDS)
1097 .removalListener(listener));
1098 Segment<Object, Object> segment = map.segments[0];
1099 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1100 assertEquals(1, table.length());
1101
1102 Object key = new Object();
1103 Object value = new Object();
1104 int hash = map.hash(key);
1105 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1106 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
1107 entry.setValueReference(valueRef);
1108
1109
1110 assertFalse(segment.reclaimValue(key, hash, valueRef));
1111
1112
1113 segment.recordWrite(entry);
1114 table.set(0, entry);
1115 segment.count = 1;
1116 assertTrue(segment.reclaimValue(key, hash, valueRef));
1117 assertEquals(1, listener.getCount());
1118 assertSame(key, listener.getLastEvictedKey());
1119 assertSame(value, listener.getLastEvictedValue());
1120 assertTrue(map.removalNotificationQueue.isEmpty());
1121 assertFalse(segment.evictionQueue.contains(entry));
1122 assertFalse(segment.expirationQueue.contains(entry));
1123 assertEquals(0, segment.count);
1124 assertNull(table.get(0));
1125
1126
1127 table.set(0, entry);
1128 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry);
1129 entry.setValueReference(otherValueRef);
1130 assertFalse(segment.reclaimValue(key, hash, valueRef));
1131 assertEquals(1, listener.getCount());
1132 assertTrue(segment.reclaimValue(key, hash, otherValueRef));
1133 assertEquals(2, listener.getCount());
1134 assertSame(key, listener.getLastEvictedKey());
1135 assertSame(value, listener.getLastEvictedValue());
1136 }
1137
1138 public void testClearValue() {
1139 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
1140 .concurrencyLevel(1)
1141 .initialCapacity(1)
1142 .maximumSize(SMALL_MAX_SIZE)
1143 .expireAfterWrite(99999, SECONDS)
1144 .removalListener(new CountingRemovalListener<Object, Object>()));
1145 Segment<Object, Object> segment = map.segments[0];
1146 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1147 assertEquals(1, table.length());
1148
1149 Object key = new Object();
1150 Object value = new Object();
1151 int hash = map.hash(key);
1152 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1153 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
1154 entry.setValueReference(valueRef);
1155
1156
1157 assertFalse(segment.clearValue(key, hash, valueRef));
1158
1159
1160 segment.recordWrite(entry);
1161 table.set(0, entry);
1162
1163 assertTrue(segment.clearValue(key, hash, valueRef));
1164
1165 assertTrue(map.removalNotificationQueue.isEmpty());
1166 assertFalse(segment.evictionQueue.contains(entry));
1167 assertFalse(segment.expirationQueue.contains(entry));
1168 assertEquals(0, segment.count);
1169 assertNull(table.get(0));
1170
1171
1172 table.set(0, entry);
1173 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry);
1174 entry.setValueReference(otherValueRef);
1175 assertFalse(segment.clearValue(key, hash, valueRef));
1176 entry.setValueReference(valueRef);
1177 assertTrue(segment.clearValue(key, hash, valueRef));
1178 }
1179
1180 private static <K, V> void assertNotificationEnqueued(
1181 MapMakerInternalMap<K, V> map, K key, V value) {
1182 RemovalNotification<K, V> notification = map.removalNotificationQueue.poll();
1183 assertSame(key, notification.getKey());
1184 assertSame(value, notification.getValue());
1185 }
1186
1187
1188
1189 public void testDrainRecencyQueueOnWrite() {
1190 for (MapMaker maker : allEvictingMakers()) {
1191 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1192 Segment<Object, Object> segment = map.segments[0];
1193
1194 if (segment.recencyQueue != DISCARDING_QUEUE) {
1195 Object keyOne = new Object();
1196 Object valueOne = new Object();
1197 Object keyTwo = new Object();
1198 Object valueTwo = new Object();
1199
1200 map.put(keyOne, valueOne);
1201 assertTrue(segment.recencyQueue.isEmpty());
1202
1203 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1204 map.get(keyOne);
1205 }
1206 assertFalse(segment.recencyQueue.isEmpty());
1207
1208 map.put(keyTwo, valueTwo);
1209 assertTrue(segment.recencyQueue.isEmpty());
1210 }
1211 }
1212 }
1213
1214 public void testDrainRecencyQueueOnRead() {
1215 for (MapMaker maker : allEvictingMakers()) {
1216 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1217 Segment<Object, Object> segment = map.segments[0];
1218
1219 if (segment.recencyQueue != DISCARDING_QUEUE) {
1220 Object keyOne = new Object();
1221 Object valueOne = new Object();
1222
1223
1224
1225 map.put(keyOne, valueOne);
1226 assertTrue(segment.recencyQueue.isEmpty());
1227
1228 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1229 map.get(keyOne);
1230 }
1231 assertFalse(segment.recencyQueue.isEmpty());
1232
1233 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1234 map.get(keyOne);
1235 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1236 }
1237
1238
1239
1240 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1241 map.put(new Object(), new Object());
1242 }
1243 assertTrue(segment.recencyQueue.isEmpty());
1244
1245 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1246 map.get(keyOne);
1247 }
1248 assertFalse(segment.recencyQueue.isEmpty());
1249
1250 for (Object key : map.keySet()) {
1251 map.get(key);
1252 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1253 }
1254 }
1255 }
1256 }
1257
1258 public void testRecordRead() {
1259 for (MapMaker maker : allEvictingMakers()) {
1260 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1261 Segment<Object, Object> segment = map.segments[0];
1262 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1263 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1264 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1265 Object key = new Object();
1266 int hash = map.hash(key);
1267 Object value = new Object();
1268
1269 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1270
1271 segment.recordWrite(entry);
1272 writeOrder.add(entry);
1273 readOrder.add(entry);
1274 }
1275
1276 checkEvictionQueues(map, segment, readOrder, writeOrder);
1277 checkExpirationTimes(map);
1278
1279
1280 Random random = new Random();
1281 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1282 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1283 while (i.hasNext()) {
1284 ReferenceEntry<Object, Object> entry = i.next();
1285 if (random.nextBoolean()) {
1286 segment.recordRead(entry);
1287 reads.add(entry);
1288 i.remove();
1289 }
1290 }
1291 checkAndDrainRecencyQueue(map, segment, reads);
1292 readOrder.addAll(reads);
1293
1294 checkEvictionQueues(map, segment, readOrder, writeOrder);
1295 checkExpirationTimes(map);
1296 }
1297 }
1298
1299 public void testRecordReadOnGet() {
1300 for (MapMaker maker : allEvictingMakers()) {
1301 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1302 Segment<Object, Object> segment = map.segments[0];
1303 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1304 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1305 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1306 Object key = new Object();
1307 int hash = map.hash(key);
1308 Object value = new Object();
1309
1310 map.put(key, value);
1311 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1312 writeOrder.add(entry);
1313 readOrder.add(entry);
1314 }
1315
1316 checkEvictionQueues(map, segment, readOrder, writeOrder);
1317 checkExpirationTimes(map);
1318 assertTrue(segment.recencyQueue.isEmpty());
1319
1320
1321 Random random = new Random();
1322 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1323 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1324 while (i.hasNext()) {
1325 ReferenceEntry<Object, Object> entry = i.next();
1326 if (random.nextBoolean()) {
1327 map.get(entry.getKey());
1328 reads.add(entry);
1329 i.remove();
1330 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1331 }
1332 }
1333 int undrainedIndex = reads.size() - segment.recencyQueue.size();
1334 checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
1335 readOrder.addAll(reads);
1336
1337 checkEvictionQueues(map, segment, readOrder, writeOrder);
1338 checkExpirationTimes(map);
1339 }
1340 }
1341
1342 public void testRecordWrite() {
1343 for (MapMaker maker : allEvictingMakers()) {
1344 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1));
1345 Segment<Object, Object> segment = map.segments[0];
1346 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1347 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1348 Object key = new Object();
1349 int hash = map.hash(key);
1350 Object value = new Object();
1351
1352 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1353
1354 segment.recordWrite(entry);
1355 writeOrder.add(entry);
1356 }
1357
1358 checkEvictionQueues(map, segment, writeOrder, writeOrder);
1359 checkExpirationTimes(map);
1360
1361
1362 Random random = new Random();
1363 List<ReferenceEntry<Object, Object>> writes = Lists.newArrayList();
1364 Iterator<ReferenceEntry<Object, Object>> i = writeOrder.iterator();
1365 while (i.hasNext()) {
1366 ReferenceEntry<Object, Object> entry = i.next();
1367 if (random.nextBoolean()) {
1368 segment.recordWrite(entry);
1369 writes.add(entry);
1370 i.remove();
1371 }
1372 }
1373 writeOrder.addAll(writes);
1374
1375 checkEvictionQueues(map, segment, writeOrder, writeOrder);
1376 checkExpirationTimes(map);
1377 }
1378 }
1379
1380 static <K, V> void checkAndDrainRecencyQueue(MapMakerInternalMap<K, V> map,
1381 Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) {
1382 if (map.evictsBySize() || map.expiresAfterAccess()) {
1383 assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue));
1384 }
1385 segment.drainRecencyQueue();
1386 }
1387
1388 static <K, V> void checkEvictionQueues(MapMakerInternalMap<K, V> map,
1389 Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder,
1390 List<ReferenceEntry<K, V>> writeOrder) {
1391 if (map.evictsBySize()) {
1392 assertSameEntries(readOrder, ImmutableList.copyOf(segment.evictionQueue));
1393 }
1394 if (map.expiresAfterAccess()) {
1395 assertSameEntries(readOrder, ImmutableList.copyOf(segment.expirationQueue));
1396 }
1397 if (map.expiresAfterWrite()) {
1398 assertSameEntries(writeOrder, ImmutableList.copyOf(segment.expirationQueue));
1399 }
1400 }
1401
1402 private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries,
1403 List<ReferenceEntry<K, V>> actualEntries) {
1404 int size = expectedEntries.size();
1405 assertEquals(size, actualEntries.size());
1406 for (int i = 0; i < size; i++) {
1407 ReferenceEntry<K, V> expectedEntry = expectedEntries.get(0);
1408 ReferenceEntry<K, V> actualEntry = actualEntries.get(0);
1409 assertSame(expectedEntry.getKey(), actualEntry.getKey());
1410 assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get());
1411 }
1412 }
1413
1414 static <K, V> void checkExpirationTimes(MapMakerInternalMap<K, V> map) {
1415 if (!map.expires()) {
1416 return;
1417 }
1418
1419 for (Segment<K, V> segment : map.segments) {
1420 long lastExpirationTime = 0;
1421 for (ReferenceEntry<K, V> e : segment.recencyQueue) {
1422 long expirationTime = e.getExpirationTime();
1423 assertTrue(expirationTime >= lastExpirationTime);
1424 lastExpirationTime = expirationTime;
1425 }
1426
1427 lastExpirationTime = 0;
1428 for (ReferenceEntry<K, V> e : segment.expirationQueue) {
1429 long expirationTime = e.getExpirationTime();
1430 assertTrue(expirationTime >= lastExpirationTime);
1431 lastExpirationTime = expirationTime;
1432 }
1433 }
1434 }
1435
1436 public void testEvictEntries() {
1437 int maxSize = 10;
1438 MapMakerInternalMap<Object, Object> map =
1439 makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize));
1440 Segment<Object, Object> segment = map.segments[0];
1441
1442
1443 int originalCount = 1024;
1444 ReferenceEntry<Object, Object> entry = null;
1445 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
1446 for (int i = 0; i < originalCount; i++) {
1447 Object key = new Object();
1448 Object value = new Object();
1449 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1450 int hash = map.hash(key);
1451 int index = hash & (table.length() - 1);
1452 ReferenceEntry<Object, Object> first = table.get(index);
1453 entry = map.newEntry(key, hash, first);
1454 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
1455 entry.setValueReference(valueRef);
1456 segment.recordWrite(entry);
1457 table.set(index, entry);
1458 originalMap.put(key, value);
1459 }
1460 segment.count = originalCount;
1461 assertEquals(originalCount, originalMap.size());
1462 assertEquals(originalMap, map);
1463
1464 for (int i = maxSize - 1; i < originalCount; i++) {
1465 assertTrue(segment.evictEntries());
1466 Iterator<Object> it = originalMap.keySet().iterator();
1467 it.next();
1468 it.remove();
1469 assertEquals(originalMap, map);
1470 }
1471 assertFalse(segment.evictEntries());
1472 }
1473
1474
1475
1476 public void testDrainKeyReferenceQueueOnWrite() {
1477 for (MapMaker maker : allKeyValueStrengthMakers()) {
1478 MapMakerInternalMap<Object, Object> map =
1479 makeMap(maker.concurrencyLevel(1));
1480 if (map.usesKeyReferences()) {
1481 Segment<Object, Object> segment = map.segments[0];
1482
1483 Object keyOne = new Object();
1484 int hashOne = map.hash(keyOne);
1485 Object valueOne = new Object();
1486 Object keyTwo = new Object();
1487 Object valueTwo = new Object();
1488
1489 map.put(keyOne, valueOne);
1490 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1491
1492 @SuppressWarnings("unchecked")
1493 Reference<Object> reference = (Reference) entry;
1494 reference.enqueue();
1495
1496 map.put(keyTwo, valueTwo);
1497 assertFalse(map.containsKey(keyOne));
1498 assertFalse(map.containsValue(valueOne));
1499 assertNull(map.get(keyOne));
1500 assertEquals(1, map.size());
1501 assertNull(segment.keyReferenceQueue.poll());
1502 }
1503 }
1504 }
1505
1506 public void testDrainValueReferenceQueueOnWrite() {
1507 for (MapMaker maker : allKeyValueStrengthMakers()) {
1508 MapMakerInternalMap<Object, Object> map =
1509 makeMap(maker.concurrencyLevel(1));
1510 if (map.usesValueReferences()) {
1511 Segment<Object, Object> segment = map.segments[0];
1512
1513 Object keyOne = new Object();
1514 int hashOne = map.hash(keyOne);
1515 Object valueOne = new Object();
1516 Object keyTwo = new Object();
1517 Object valueTwo = new Object();
1518
1519 map.put(keyOne, valueOne);
1520 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1521 ValueReference<Object, Object> valueReference = entry.getValueReference();
1522
1523 @SuppressWarnings("unchecked")
1524 Reference<Object> reference = (Reference) valueReference;
1525 reference.enqueue();
1526
1527 map.put(keyTwo, valueTwo);
1528 assertFalse(map.containsKey(keyOne));
1529 assertFalse(map.containsValue(valueOne));
1530 assertNull(map.get(keyOne));
1531 assertEquals(1, map.size());
1532 assertNull(segment.valueReferenceQueue.poll());
1533 }
1534 }
1535 }
1536
1537 public void testDrainKeyReferenceQueueOnRead() {
1538 for (MapMaker maker : allKeyValueStrengthMakers()) {
1539 MapMakerInternalMap<Object, Object> map =
1540 makeMap(maker.concurrencyLevel(1));
1541 if (map.usesKeyReferences()) {
1542 Segment<Object, Object> segment = map.segments[0];
1543
1544 Object keyOne = new Object();
1545 int hashOne = map.hash(keyOne);
1546 Object valueOne = new Object();
1547 Object keyTwo = new Object();
1548
1549 map.put(keyOne, valueOne);
1550 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1551
1552 @SuppressWarnings("unchecked")
1553 Reference<Object> reference = (Reference) entry;
1554 reference.enqueue();
1555
1556 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
1557 map.get(keyTwo);
1558 }
1559 assertFalse(map.containsKey(keyOne));
1560 assertFalse(map.containsValue(valueOne));
1561 assertNull(map.get(keyOne));
1562 assertEquals(0, map.size());
1563 assertNull(segment.keyReferenceQueue.poll());
1564 }
1565 }
1566 }
1567
1568 public void testDrainValueReferenceQueueOnRead() {
1569 for (MapMaker maker : allKeyValueStrengthMakers()) {
1570 MapMakerInternalMap<Object, Object> map =
1571 makeMap(maker.concurrencyLevel(1));
1572 if (map.usesValueReferences()) {
1573 Segment<Object, Object> segment = map.segments[0];
1574
1575 Object keyOne = new Object();
1576 int hashOne = map.hash(keyOne);
1577 Object valueOne = new Object();
1578 Object keyTwo = new Object();
1579
1580 map.put(keyOne, valueOne);
1581 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
1582 ValueReference<Object, Object> valueReference = entry.getValueReference();
1583
1584 @SuppressWarnings("unchecked")
1585 Reference<Object> reference = (Reference) valueReference;
1586 reference.enqueue();
1587
1588 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
1589 map.get(keyTwo);
1590 }
1591 assertFalse(map.containsKey(keyOne));
1592 assertFalse(map.containsValue(valueOne));
1593 assertNull(map.get(keyOne));
1594 assertEquals(0, map.size());
1595 assertNull(segment.valueReferenceQueue.poll());
1596 }
1597 }
1598 }
1599
1600
1601
1602
1603
1604
1605
1606 private static Iterable<MapMaker> allEntryTypeMakers() {
1607 List<MapMaker> result = newArrayList(allKeyValueStrengthMakers());
1608 for (MapMaker maker : allKeyValueStrengthMakers()) {
1609 result.add(maker.maximumSize(SMALL_MAX_SIZE));
1610 }
1611 for (MapMaker maker : allKeyValueStrengthMakers()) {
1612 result.add(maker.expireAfterAccess(99999, SECONDS));
1613 }
1614 for (MapMaker maker : allKeyValueStrengthMakers()) {
1615 result.add(maker.expireAfterWrite(99999, SECONDS));
1616 }
1617 for (MapMaker maker : allKeyValueStrengthMakers()) {
1618 result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterAccess(99999, SECONDS));
1619 }
1620 for (MapMaker maker : allKeyValueStrengthMakers()) {
1621 result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterWrite(99999, SECONDS));
1622 }
1623 return result;
1624 }
1625
1626
1627
1628
1629 static Iterable<MapMaker> allEvictingMakers() {
1630 return ImmutableList.of(createMapMaker().maximumSize(SMALL_MAX_SIZE),
1631 createMapMaker().expireAfterAccess(99999, SECONDS),
1632 createMapMaker().expireAfterWrite(99999, SECONDS),
1633 createMapMaker()
1634 .maximumSize(SMALL_MAX_SIZE)
1635 .expireAfterAccess(SMALL_MAX_SIZE, TimeUnit.SECONDS),
1636 createMapMaker()
1637 .maximumSize(SMALL_MAX_SIZE)
1638 .expireAfterWrite(SMALL_MAX_SIZE, TimeUnit.SECONDS));
1639 }
1640
1641
1642
1643
1644 private static Iterable<MapMaker> allKeyValueStrengthMakers() {
1645 return ImmutableList.of(createMapMaker(),
1646 createMapMaker().weakValues(),
1647 createMapMaker().softValues(),
1648 createMapMaker().weakKeys(),
1649 createMapMaker().weakKeys().weakValues(),
1650 createMapMaker().weakKeys().softValues());
1651 }
1652
1653
1654
1655 private static class CountingRemovalListener<K, V> implements RemovalListener<K, V> {
1656 private final AtomicInteger count = new AtomicInteger();
1657 private K lastKey;
1658 private V lastValue;
1659
1660 @Override
1661 public void onRemoval(RemovalNotification<K, V> notification) {
1662 count.incrementAndGet();
1663 lastKey = notification.getKey();
1664 lastValue = notification.getValue();
1665 }
1666
1667 public int getCount() {
1668 return count.get();
1669 }
1670
1671 public K getLastEvictedKey() {
1672 return lastKey;
1673 }
1674
1675 public V getLastEvictedValue() {
1676 return lastValue;
1677 }
1678 }
1679
1680 static class QueuingRemovalListener<K, V>
1681 extends ConcurrentLinkedQueue<RemovalNotification<K, V>> implements RemovalListener<K, V> {
1682 @Override
1683 public void onRemoval(RemovalNotification<K, V> notification) {
1684 add(notification);
1685 }
1686 }
1687
1688
1689
1690 private static <K, V> DummyEntry<K, V> createDummyEntry(
1691 K key, int hash, V value, ReferenceEntry<K, V> next) {
1692 DummyEntry<K, V> entry = DummyEntry.create(key, hash, next);
1693 DummyValueReference<K, V> valueRef = DummyValueReference.create(value, entry);
1694 entry.setValueReference(valueRef);
1695 return entry;
1696 }
1697
1698 static class DummyEntry<K, V> implements ReferenceEntry<K, V> {
1699 private K key;
1700 private final int hash;
1701 private final ReferenceEntry<K, V> next;
1702
1703 public DummyEntry(K key, int hash, ReferenceEntry<K, V> next) {
1704 this.key = key;
1705 this.hash = hash;
1706 this.next = next;
1707 }
1708
1709 public static <K, V> DummyEntry<K, V> create(K key, int hash, ReferenceEntry<K, V> next) {
1710 return new DummyEntry<K, V>(key, hash, next);
1711 }
1712
1713 public void clearKey() {
1714 this.key = null;
1715 }
1716
1717 private ValueReference<K, V> valueReference = unset();
1718
1719 @Override
1720 public ValueReference<K, V> getValueReference() {
1721 return valueReference;
1722 }
1723
1724 @Override
1725 public void setValueReference(ValueReference<K, V> valueReference) {
1726 this.valueReference = valueReference;
1727 }
1728
1729 @Override
1730 public ReferenceEntry<K, V> getNext() {
1731 return next;
1732 }
1733
1734 @Override
1735 public int getHash() {
1736 return hash;
1737 }
1738
1739 @Override
1740 public K getKey() {
1741 return key;
1742 }
1743
1744 private long expirationTime = Long.MAX_VALUE;
1745
1746 @Override
1747 public long getExpirationTime() {
1748 return expirationTime;
1749 }
1750
1751 @Override
1752 public void setExpirationTime(long time) {
1753 this.expirationTime = time;
1754 }
1755
1756 private ReferenceEntry<K, V> nextExpirable = nullEntry();
1757
1758 @Override
1759 public ReferenceEntry<K, V> getNextExpirable() {
1760 return nextExpirable;
1761 }
1762
1763 @Override
1764 public void setNextExpirable(ReferenceEntry<K, V> next) {
1765 this.nextExpirable = next;
1766 }
1767
1768 private ReferenceEntry<K, V> previousExpirable = nullEntry();
1769
1770 @Override
1771 public ReferenceEntry<K, V> getPreviousExpirable() {
1772 return previousExpirable;
1773 }
1774
1775 @Override
1776 public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
1777 this.previousExpirable = previous;
1778 }
1779
1780 private ReferenceEntry<K, V> nextEvictable = nullEntry();
1781
1782 @Override
1783 public ReferenceEntry<K, V> getNextEvictable() {
1784 return nextEvictable;
1785 }
1786
1787 @Override
1788 public void setNextEvictable(ReferenceEntry<K, V> next) {
1789 this.nextEvictable = next;
1790 }
1791
1792 private ReferenceEntry<K, V> previousEvictable = nullEntry();
1793
1794 @Override
1795 public ReferenceEntry<K, V> getPreviousEvictable() {
1796 return previousEvictable;
1797 }
1798
1799 @Override
1800 public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
1801 this.previousEvictable = previous;
1802 }
1803 }
1804
1805 static class DummyValueReference<K, V> implements ValueReference<K, V> {
1806 final ReferenceEntry<K, V> entry;
1807 private V value;
1808
1809 public DummyValueReference(V value, ReferenceEntry<K, V> entry) {
1810 this.value = value;
1811 this.entry = entry;
1812 }
1813
1814 public static <K, V> DummyValueReference<K, V> create(V value, ReferenceEntry<K, V> entry) {
1815 return new DummyValueReference<K, V>(value, entry);
1816 }
1817
1818 @Override
1819 public V get() {
1820 return value;
1821 }
1822
1823 @Override
1824 public ReferenceEntry<K, V> getEntry() {
1825 return entry;
1826 }
1827
1828 @Override
1829 public ValueReference<K, V> copyFor(
1830 ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
1831 return new DummyValueReference<K, V>(value, entry);
1832 }
1833
1834 boolean computing = false;
1835
1836 public void setComputing(boolean computing) {
1837 this.computing = computing;
1838 }
1839
1840 @Override
1841 public boolean isComputingReference() {
1842 return computing;
1843 }
1844
1845 @Override
1846 public V waitForValue() {
1847 return get();
1848 }
1849
1850 @Override
1851 public void clear(ValueReference<K, V> newValue) {
1852 value = null;
1853 }
1854 }
1855
1856 public void testNullParameters() throws Exception {
1857 NullPointerTester tester = new NullPointerTester();
1858 tester.testAllPublicInstanceMethods(makeMap(createMapMaker()));
1859 }
1860
1861 }